﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmInterview.Chapter01._01;

/// <summary>
/// 方法二：递归法
/// </summary>
public class Test02
{
    /// <summary>
    /// 对不带头结点的单链表进行排序
    /// </summary>
    /// <param name="head"></param>
    /// <returns></returns>
    private static LNode RecursiveReverse(LNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
        else
        {
            // 反转后面的结点
            LNode newhead = RecursiveReverse(head.next);
            // 把当前遍历的结点加到后面结点逆序后链表的尾部
            head.next.next = head;
            head.next = null;
            return newhead;
        }
    }

    /// <summary>
    /// 对带头结点的单链表进行逆序
    /// </summary>
    /// <param name="head"></param>
    public static void Reverse(LNode head)
    {
        if (head == null)
            return;
        // 获取链表的第一个结点
        LNode firstNode = head.next;
        // 对链表进行逆序
        LNode newhead = RecursiveReverse(firstNode);
        // 头结点指向逆序后链表的第一个结点
        head.next = newhead;
    }
}